package leetcode_21_40;

public class searchInsert_35 {
    /**
     * 一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
     * 如果目标值不存在于数组中，返回它将会被按顺序插入的位置
     * 必须使用时间复杂度为 O(log n) 的算法。
     * @param nums
     * @param target
     * @return
     */
    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1, ans = 0;
        if(target>nums[right])
            return right+1;
        if(target<nums[left])
            return 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid]==target){          //有对应的值就退出
                ans=mid;
                break;
            }else if(nums[mid] > target){  //不进行加一减一操作，每次转区间都连带着mid

                right=mid;
            }else {
                left=mid;
                if(right==left+1){   //如果不含有target值，最终必然剩下连续的两个值
                                                 //left<target<right
                    ans=right;
                    break;
                }
            }
        }
        return ans;
    }
}
